package leetcode.leetcode_106;

import java.util.Arrays;

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, postorder);
    }
    public TreeNode build (int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        int val = postorder[postorder.length - 1];
        TreeNode treeNode = new TreeNode(val);
        int i = findIndex(inorder, val);
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, i);
        int[] RightInorder = Arrays.copyOfRange(inorder, i + 1, inorder.length);
        int[] leftPostorder = Arrays.copyOfRange(postorder, 0, i);
        int[] rightPostorder = Arrays.copyOfRange(postorder, i, postorder.length-1);
        treeNode.left = build(leftInorder, leftPostorder);
        treeNode.right = build(RightInorder, rightPostorder);
        return treeNode;

    }
    public int findIndex (int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}